//
// Created by dengspc on 2019/1/10.
//

#ifndef INC_010_ALGORITHM_HEAP_H
#define INC_010_ALGORITHM_HEAP_H

#include <iostream>
#include <ctime>
#include <cassert>
#include <algorithm>
#include <typeinfo>
#include <cmath>

using namespace std;

template<typename Item>
class MaxHeap{
private:
    Item *data;
    int count;
    int capcity;

    void shiftUp(int p) {
        int k = p/2;
        while(k>=1 && data[p]>data[k]){
            swap(data[k],data[p]);
            p = k;
            k = p/2;
        }
    }

    void shiftDown(int k) {
        while(k*2<=count){
            int j = k*2;
            if(j+1<=count && data[j+1]>data[j]){
                j++;
            }
            if(data[j]<data[k]) break;
            swap(data[j],data[k]);
            k=j;
        }
    }
public:
    MaxHeap(int capacity){
        data = new Item[capacity+1];
        count = 0;
        this->capcity = capacity;
    }

    MaxHeap(Item arr[], int n){
        data = new Item[n+1];
        count = n;
        this->capcity = n;
        for(int i = 1;i<=n;i++){
            data[i] = arr[i-1];
        }
        for(int i = n/2;i>=1;i--){
            shiftDown(i);
        }
    }

    ~MaxHeap(){
        delete[] data;
    }

    int size(){
        return count;
    }

    bool isEmpty(){
        return count == 0;
    }

    void insert(Item insert){
        assert(count<capcity);
        data[++count] = insert;
        shiftUp(count);
    }

    Item pop(){
        assert(count!=0);
        Item result = data[1];
        swap(data[count],data[1]);
        count--;
        shiftDown(1);
        return result;
    }
public:
    void testPrint(){

        if( size() >= 100 ){
            cout<<"Fancy print can only work for less than 100 int";
            return;
        }

        if( typeid(Item) != typeid(int) ){
            cout <<"Fancy print can only work for int item";
            return;
        }

        cout<<"The Heap size is: "<<size()<<endl;
        cout<<"data in heap: ";
        for( int i = 1 ; i <= size() ; i ++ )
            cout<<data[i]<<" ";
        cout<<endl;
        cout<<endl;

        int n = size();
        int max_level = 0;
        int number_per_level = 1;
        while( n > 0 ) {
            max_level += 1;
            n -= number_per_level;
            number_per_level *= 2;
        }

        int max_level_number = int(pow(2, max_level-1));
        int cur_tree_max_level_number = max_level_number;
        int index = 1;
        for( int level = 0 ; level < max_level ; level ++ ){
            string line1 = string(max_level_number*3-1, ' ');

            int cur_level_number = min(count-int(pow(2,level))+1,int(pow(2,level)));
            bool isLeft = true;
            for( int index_cur_level = 0 ; index_cur_level < cur_level_number ; index ++ , index_cur_level ++ ){
                putNumberInLine( data[index] , line1 , index_cur_level , cur_tree_max_level_number*3-1 , isLeft );
                isLeft = !isLeft;
            }
            cout<<line1<<endl;

            if( level == max_level - 1 )
                break;

            string line2 = string(max_level_number*3-1, ' ');
            for( int index_cur_level = 0 ; index_cur_level < cur_level_number ; index_cur_level ++ )
                putBranchInLine( line2 , index_cur_level , cur_tree_max_level_number*3-1 );
            cout<<line2<<endl;

            cur_tree_max_level_number /= 2;
        }
    }

private:
    void putNumberInLine( int num, string &line, int index_cur_level, int cur_tree_width, bool isLeft){

        int sub_tree_width = (cur_tree_width - 1) / 2;
        int offset = index_cur_level * (cur_tree_width+1) + sub_tree_width;
        assert(offset + 1 < line.size());
        if( num >= 10 ) {
            line[offset + 0] = '0' + num / 10;
            line[offset + 1] = '0' + num % 10;
        }
        else{
            if( isLeft)
                line[offset + 0] = '0' + num;
            else
                line[offset + 1] = '0' + num;
        }
    }

    void putBranchInLine( string &line, int index_cur_level, int cur_tree_width){

        int sub_tree_width = (cur_tree_width - 1) / 2;
        int sub_sub_tree_width = (sub_tree_width - 1) / 2;
        int offset_left = index_cur_level * (cur_tree_width+1) + sub_sub_tree_width;
        assert( offset_left + 1 < line.size() );
        int offset_right = index_cur_level * (cur_tree_width+1) + sub_tree_width + 1 + sub_sub_tree_width;
        assert( offset_right < line.size() );

        line[offset_left + 1] = '/';
        line[offset_right + 0] = '\\';
    }
};

#endif //INC_010_ALGORITHM_HEAP_H
